\documentclass[supercite]{Experimental_Report}

\title{~~~~~~计算机系统结构实验~~~~~~}
\author{崔昊阳}
\school{计算机科学与技术学院}
\classnum{CS2104}
\stunum{U202115415}
\instructor{童薇}
\date{2024年5月1日}

\usepackage{algorithm, multirow}
\usepackage{algpseudocode}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{mathtools}
\usepackage{subcaption}
\usepackage{xltxtra} %提供了针对XeTeX的改进并且加入了XeTeX的LOGO, 自动调用xunicode宏包(提供Unicode字符宏)
\usepackage{bm}
\usepackage{tikz}
\usepackage{tikzscale}
\usepackage{pgfplots}
%\usepackage{enumerate}

\pgfplotsset{compat=1.16}

\newcommand{\cfig}[3]{
  \begin{figure}[htb]
    \centering
    \includegraphics[width=#2\textwidth]{images/#1.tikz}
    \caption{#3}
    \label{fig:#1}
  \end{figure}
}

\newcommand{\sfig}[3]{
  \begin{subfigure}[b]{#2\textwidth}
    \includegraphics[width=\textwidth]{images/#1.tikz}
    \caption{#3}
    \label{fig:#1}
  \end{subfigure}
}

\newcommand{\xfig}[3]{
  \begin{figure}[htb]
    \centering
    #3
    \caption{#2}
    \label{fig:#1}
  \end{figure}
}

\newcommand{\rfig}[1]{\autoref{fig:#1}}
\newcommand{\ralg}[1]{\autoref{alg:#1}}
\newcommand{\rthm}[1]{\autoref{thm:#1}}
\newcommand{\rlem}[1]{\autoref{lem:#1}}
\newcommand{\reqn}[1]{\autoref{eqn:#1}}
\newcommand{\rtbl}[1]{\autoref{tbl:#1}}

\algnewcommand\Null{\textsc{null }}
\algnewcommand\algorithmicinput{\textbf{Input:}}
\algnewcommand\Input{\item[\algorithmicinput]}
\algnewcommand\algorithmicoutput{\textbf{Output:}}
\algnewcommand\Output{\item[\algorithmicoutput]}
\algnewcommand\algorithmicbreak{\textbf{break}}
\algnewcommand\Break{\algorithmicbreak}
\algnewcommand\algorithmiccontinue{\textbf{continue}}
\algnewcommand\Continue{\algorithmiccontinue}
\algnewcommand{\LeftCom}[1]{\State $\triangleright$ #1}

\newtheorem{thm}{定理}[section]
\newtheorem{lem}{引理}[section]

\colorlet{shadecolor}{black!15}

\theoremstyle{definition}
\newtheorem{alg}{算法}[section]

\def\thmautorefname~#1\null{定理~#1~\null}
\def\lemautorefname~#1\null{引理~#1~\null}
\def\algautorefname~#1\null{算法~#1~\null}

\begin{document}

\maketitle

\clearpage

\pagenumbering{Roman}

\tableofcontents[level=2]

\clearpage

\pagenumbering{arabic}

\section{Cache 模拟器实验}
\subsection{实验目的}
\label{实验目的}
本实验要求在 csim.c 提供的程序框架中，编写实现一个 Cache 模拟器。
模拟器需要根据内存访问轨迹文件中的内容和命令行输入的组索引的位数（s）、每一组包含的行数（E）以及偏移位的宽度（b）来模拟一个组相联 Cache 的运行轨迹
并输出命中、缺失和（缓存行）脱胎/驱除（基于LRU算法）的总数。

\subsection{实验环境}
本实验在本地和远程（头歌）皆可运行，其中远程（头歌）的实验环境如表\ref{远程实验环境}所示。本地的实验环境如表\ref{本地实验环境}所示（我修改了 \texttt{driver.py} 代码使之可以在 Python3 下运行）。
\begin{table}[H]
	\centering
	\caption{远程实验环境}
	  \begin{tabular}{|c|c|c|}
		\toprule
	  \multirow{4}[0]{*}{硬件环境} & CPU架构 & x86\_64 \\\cmidrule{2-3}
			& CPU型号 & Intel(R)Xeon(R)Platinum8269CYCPU@2.50GHz \\\cmidrule{2-3}
			& CPU核数 & 16 \\\cmidrule{2-3}
			& 主存容量  & 31G \\
			\midrule
	  \multirow{3}[0]{*}{软件环境} & 操作系统  & DebianGNU/Linux9(stretch) \\\cmidrule{2-3}
			& GCC版本 & 7.3.0 \\\cmidrule{2-3}
			& Python版本 & 2.7.13 \\
		\bottomrule
	  \end{tabular}
	\label{远程实验环境}
\end{table}

\begin{table}[H]
	\centering
	\caption{本地实验环境}
	  \begin{tabular}{|c|c|c|}
		\toprule
	  \multirow{4}[0]{*}{硬件环境} & CPU架构 & x86\_64 \\\cmidrule{2-3}
			& CPU型号 & 11th Gen Intel(R) Core(TM) i7-11800H @ 2.30GHz \\\cmidrule{2-3}
			& CPU核数 & 16 \\\cmidrule{2-3}
			& 主存容量  & 16G \\
			\midrule
	  \multirow{3}[0]{*}{软件环境} & 操作系统  & Ubuntu on WSL2 \\\cmidrule{2-3}
			& GCC版本 & 11.4.0 \\\cmidrule{2-3}
			& Python版本 & 3.7.0 \\
		\bottomrule
	  \end{tabular}
	\label{本地实验环境}
\end{table}

\subsection{实验思路}
为了实现\ref{实验目的}中要求的功能，我们需要设计\textbf{组相联 Cache 的数据结构}，\textbf{Cache 访问、更新的方法}以及\textbf{命令行解析}，\textbf{内存访问轨迹解析}算法。
下面，我将分别展示这 4 个内容的实现思路和方法。

\subsubsection{Cache 的数据结构}
首先，我们设计Cache 的数据结构。组相联 Cache 由若干个 Cache 组构成，每个 Cache 组又可分为若干 Cache 行。
每个 Cache 行中包含用于索引的标记（tag）、用于 LRU 淘汰的计时器（timer）以及标记是否有效的有效位（valid）。
由于 Cache 模拟器不关心 Cache 中存储的具体信息，所以我不设置存储数据的比特位。

根据上述信息，我设计了 Cache 行结构体（\texttt{Line}）、Cache 组结构体（\texttt{Group}）和 Cache 整体结构体（\texttt{Cache}）。
其中，Cache 行结构体包含标记是否有效的有效位 \texttt{valid} 、用于索引的标记 \texttt{tag} 以及用于 LRU 淘汰的计时器 \texttt{timer}，
Cache 组结构体包含一个 Cache 行结构体数组 \texttt{lines} 和 Cache 行数组中元素的数量（即每一组包含的行数）\texttt{num}。
Cache 整体结构体包含一个 Cache 组结构体数组 \texttt{groups} 、组索引的位数 \texttt{group\_bits} 和偏移位的宽度 \texttt{offset\_bits}。
具体代码如\ref{Cache数据结构}所示。
\begin{figure}[H]
	\begin{center}
		\includegraphics[scale=0.20]{images/Cache数据结构.png}
		\caption{Cache 数据结构的代码实现}
		\label{Cache数据结构}
	\end{center}
\end{figure}

设计完 Cache 结构体后，我还需要根据在命令行中解析到的组索引位数 \texttt{s}、每一组包含的行数 \texttt{E} 和偏移位的宽度 \texttt{b} 建立一个 Cache 实例并为其分配空间。
对应地，在模拟完成之后，还需要释放 Cache 实例的空间。实例建立函数 \texttt{build\_cache} 和实例释放函数 \texttt{destroy\_cache} 的具体代码如\ref{实例建立释放}所示。
\begin{figure}[H]
	\begin{center}
		\includegraphics[scale=0.20]{images/实例建立释放.png}
		\caption{Cache 实例的建立和释放}
		\label{实例建立释放}
	\end{center}
\end{figure}

\subsubsection{Cache 的访问和更新}
接着，我们设计 Cache 的访问和更新的算法：\texttt{access\_cache()} 和 \texttt{update()}。

Cache 的访问函数接收指向要访问的 Cache 的指针和一个地址。首先，函数根据传入的地址计算出标记（\texttt{tag}）和组索引（\texttt{idx}）。
接着，函数遍历一遍组索引指向的 Cache 组内的所有 Cache 行，在这遍遍历中，函数在寻找是否有有效行的标记和要访问的地址的标记相等的同时，
还要找到索引最小的空闲行（如果有的话）和当前计时器值最小的有效行（即按 LRU 算法需要淘汰的行）。遍历结束后，若找到了标记和要访问的地址的标记相等的有效行，
则访问命中，命中次数自增 1, 并数按 LRU 算法更新计时器。若未找到，则说明访问未命中。函数将未命中次数自增 1，再查看是否找到了空闲行。
若找到了空闲行，则向空闲行写入要访问的行即可。若未找到空闲行，则淘汰次数自增1，淘汰之前找到的要淘汰的行并在这一行写入要访问的行。
\texttt{access\_cache()} 函数的具体代码如\ref{access函数}所示。
\begin{figure}[H]
	\begin{center}
		\includegraphics[scale=0.25]{images/access函数.png}
		\caption{access\_cache() 函数的具体代码}
		\label{access函数}
	\end{center}
\end{figure}

Cache 的更新函数接收指向要访问的 Cache 的指针、组索引、组内的行索引和新的标记。首先，函数根据传入的组索引和组内的行索引定位到要更新的行和其所在的组。
接着，函数将 Cache 行的标记修改成新的标记并将有效位置 1。然后，函数遍历该行所在的组，按 LRU 算法的规则，将所有有效行中计时器值大于旧的行的计时器值的行的计时器值自减 1。
最后，将更新的行的计时器值置为最大（即组中行总数减 1）。\texttt{update()} 函数的具体代码如\ref{update函数}所示。
\begin{figure}[H]
	\begin{center}
		\includegraphics[scale=0.20]{images/update函数.png}
		\caption{update() 函数的具体代码}
		\label{update函数}
	\end{center}
\end{figure}

\subsubsection{命令行解析}
至此，我们完成了 Cache 模拟器的所有核心功能的实现。接着，我们编写模拟器和命令行交互的代码。

我们使用 C 语言的 \texttt{getopt.h} 库提供的 \texttt{getopt()} 函数来读入命令行中的参数。\texttt{getopt()} 函数接收 \texttt{main()} 函数的 \texttt{argc} 和 \texttt{argv} 以及一个表示命令选项的字符串。
根据\label{实验目的}，我可以这样调用这个函数：\texttt{getopt(argc, argv, "hvs:E:b:t:")}。
函数类似于一个迭代器，一次迭代返回一个编译选项，编译选项的值存放在 \texttt{optarg} 中，当读取结束时，函数返回 -1。
所以，可以通过\ref{命令行解析}来获得 Cache 模拟器的组索引位数 \texttt{s}、每一组包含的行数 \texttt{E} 、偏移位的宽度 \texttt{b} 和内存访问轨迹文件的路径。
\begin{figure}[H]
	\begin{center}
		\includegraphics[scale=0.20]{images/命令行解析.png}
		\caption{命令行解析代码}
		\label{命令行解析}
	\end{center}
\end{figure}

\subsubsection{内存访问轨迹解析}
通过命令行获得内存访问轨迹文件的路径后，我们即可打开这个文件并读取其内容。内存访问轨迹文件的一行表示一次对 Cache 的访问。
一行的格式为：[命令代码][space][地址],[数据长度]。命令代码为 \texttt{I} 时，表示指令加载，模拟器会忽略这个指令。
命令代码为 \texttt{M} 时，表示数据修改，即数据存储之后的数据加载。所以修改命令需要访问两次 Cache。其余的指令会访问 1 次 Cache。
具体代码如\ref{内存访问轨迹解析}。
\begin{figure}[H]
	\begin{center}
		\includegraphics[scale=0.20]{images/内存访问轨迹解析.png}
		\caption{内存访问轨迹解析代码}
		\label{内存访问轨迹解析}
	\end{center}
\end{figure}


至此，我们就完成了实验思路的设计和实验代码的编写。
\subsection{实验结果和分析}
接下来，我们在本地编译并运行 Cache 模拟器。首先使用 gcc 编译代码：\texttt{gcc -g -Wall -Werror -std=c11 -m64 -o csim csim.c cachelab.c -lm}，
接着运行模拟器 \texttt{./csim -s 4 -E 1 -b 4 -t traces/yi.trace}。结果如\ref{cache结果1}所示。
\begin{figure}[H]
	\begin{center}
		\includegraphics[scale=0.5]{images/cache结果1.png}
		\caption{结果1}
		\label{cache结果1}
	\end{center}
\end{figure}
然后运行测试 \texttt{bash step1.sh}，结果如图\ref{cache结果2}所示，可见结果全部正确。本代码在头歌上也可以通过。
\begin{figure}[H]
	\begin{center}
		\includegraphics[scale=0.13]{images/cache结果2.png}
		\caption{结果2}
		\label{cache结果2}
	\end{center}
\end{figure}

\newpage
\section{优化矩阵转置}
\subsection{实验目的}
本实验要求在 \texttt{trans.c} 中使用 C 语言编写一个实现矩阵转置的函数 \texttt{trans-\\pose\_submit()}，
并且使函数调用过程中对 cache 的不命中数 miss 尽可能少。

\subsection{实验环境}
本实验在本地和远程（头歌）皆可运行，其中远程（头歌）的实验环境如表\ref{远程实验环境}所示。本地的实验环境如表\ref{本地实验环境}所示（我修改了 \texttt{driver\_tans.py} 代码使之可以在 Python3 下运行）。

\subsection{实验思路}
首先，我们查看 \texttt{test-trans.c} 以获取本实验使用的 Cache 的相关参数。从测试程序中可知，本实验所使用的 Cache 满足$s=5, E=1, b=5$。
即每组中仅有一行，一行有 32 B，即可存储 8 个整型变量。

我们发现，相比于要转置的矩阵，由于相比于要转置的矩阵，Cache 的容量显著偏小。这样以来，若按照朴素方法进行矩阵转置操作，那么 Cache 满后会发生频繁的未命中现象，从而影响 CPU 访问主存的速度。
所以，我们需要对矩阵转置算法进行针对 Cache 的优化，以减小 CPU 访问主存的时间开销。

由于 Cache 一行的容量为 8 个整数，所以我们首先采取分块的思想，将 A 矩阵和 B 矩阵都分成 $8\times 8$ 的块，一次处理 A 的一块和对应的 B 的那一块。
为了方便叙述，我们在下面的叙述中将 A 矩阵的一块称为 A，B 矩阵的对应的那一块称为 B。同时，我们用类似于 Python 语法的语言来描述赋值操作。这一步骤的代码如\ref{代码1}所示。
\begin{figure}[H]
	\begin{center}
		\includegraphics[scale=0.2]{images/代码1.png}
		\caption{步骤 1 的代码}
		\label{代码1}
	\end{center}
\end{figure}

接着，在每一块中，我们首先将 A 中的第 \texttt{i} 行全部存入 \texttt{t0} 到 \texttt{t7} 的临时变量中，即 \texttt{t0:t7 = A[i, :]}。
接着，将 \texttt{t0:t3} 赋值到 B 矩阵的对应位置，即 \texttt{B[:4, i] = t0:t3}。同时为了提高缓存命中率，我们先不将 \texttt{t4:t7} 放到正确位置，而是先将其
暂时存到 \texttt{B[:4, 4 + i]} 中，即 \texttt{B[:4, 4 + i] = t4:t7}。在上述过程中，\texttt{i} 从 0 迭代到 3。这一步骤的代码如\ref{代码2}所示。
\begin{figure}[H]
	\begin{center}
		\includegraphics[scale=0.2]{images/代码2.png}
		\caption{步骤 2 的代码}
		\label{代码2}
	\end{center}
\end{figure}

进行完上述过程后，B 矩阵的子矩阵 \texttt{B[:4, :4]} 已经是正确的转置状态，但 \texttt{B[:4, 4:]} 应该被平移到 \texttt{B[4:, :4]} 子矩阵中去。
为了，提高这个过程中的缓存命中率，我们采用如下方式进行平移。首先将 \texttt{B[i, 4:]} 这 4 个元素赋值到临时变量中去，\texttt{t0:t3 = B[i, 4:]}。
并将 \texttt{A[4:, i]} 赋值到临时变量中去，\texttt{t4:t7 = A[4:, i]}。然后，我们将 \texttt{t4:t7} 赋值到 \texttt{B[i, 4:]} 中，即 \texttt{B[i, 4:] = t4:t7}。
这时，B 矩阵的第 \texttt{i} 行已是正确转置后的结果。我们将 \texttt{A[4:, 4 + i]} 赋值到 \texttt{t4:t7} 中，\texttt{t4:t7 = A[4:, 4 + i]}，并紧接着将其
赋值到 \texttt{B[4 + i, 4:]} 中，\texttt{B[4 + i, 4:] = t4:t7}。最后，将 \texttt{t0:t3} 赋值到 \texttt{B[4 + i, :4]}，\texttt{B[4 + i, :4] = t0:t3}。
在上述过程中，\texttt{i} 从 0 迭代到 3。至此，我们就完成了 A 矩阵的转置。这一步骤的代码如\ref{代码3}所示。
\begin{figure}[H]
	\begin{center}
		\includegraphics[scale=0.2]{images/代码3.png}
		\caption{步骤 3 的代码}
		\label{代码3}
	\end{center}
\end{figure}

最后，为了解决行数或列数有可能不是 8 的倍数的问题，我们需要单独处理行和列最后剩余的不足 8 的部分。在这个部分中，我们简单的采取朴素做法。

可以证明，对于 $32\times 32$ 、$64\times 64$ 和 $61\times 67$ 的矩阵，上述过程中缓存的命中率都明显大于朴素做法。

\subsection{实验结果和分析}

接下来，我们在本地编译并运行转置函数测试程序。运行测试 \texttt{bash step2.sh}，info 文件的内容如图\ref{trans结果}所示，可见优化效果明显。本代码在头歌上也可以通过。
\begin{figure}[H]
	\begin{center}
		\includegraphics[scale=0.8]{images/trans结果.png}
		\caption{结果}
		\label{trans结果}
	\end{center}
\end{figure}

\newpage
\section{总结和体会}
本实验的两个任务分别围绕 Cache 的模拟和矩阵转置算法针对 Cache 的优化展开。
通过完成组相联 Cache 模拟器以及对矩阵转置算法做针对 Cache 的优化使 Cache 不命中次数尽量少，
我我深刻理解了 Cache 的工作原理及其在提升计算机系统性能中的关键作用。

在设计组相联 Cache 模拟器的过程中，我不仅知道了如何模拟 Cache 的访问、更新操作，还更深入地理解了块大小、替换策略、缓存行等 Cache 重要概念。
在矩阵转置算法的优化部分，我深入理解了数据访问模式如何影响 Cache 效率。矩阵转置时，原始算法可能导致频繁的 Cache 不命中，而通过对算法进行针对性优化，我们可以有效地减少数据的访问冲突，提高 Cache 的利用率。
这个过程让我对算法设计有了更深的理解，明白了在算法的优化过程中，我们不仅要考虑时间复杂度的降低，还要关注数据存储和访问的效率的提高。

此外，实验也让我体验到了理论知识与实践操作相结合的重要性。理论上的 Cache 知识在实际模拟和优化中得到了验证和深化，而实践中遇到的问题又反哺了我对理论的理解。总而验证，本次实验是一次极好的理论与实践相结合的学习经历。

\section{对实验课程的建议}
在完成实验后，我对实验有以下的三点建议：
\begin{enumerate}
	\item 在实验一中，答案以源码的形式放在 \texttt{csim-ref.c} 中。建议将源码编译成可执行程序后再放入头歌的工作目录中。
	\item 在实验二中，从头开始想一个矩阵转置优化算法难度较大，且头歌中的提示有些语焉不详。建议将提示写得更详细一些。
	\item 建议提供实验报告的 \LaTeX 模板，减少同学们在书写报告时花费在调整格式方面的时间。
\end{enumerate}

\end{document}